\documentclass{beamer}

% \usepackage{beamerthemesplit} // Activate for custom appearance
\usepackage{k}
\usepackage{color}

\title{Automating Abstract Syntax Tree construction for Context Free Grammars}
\author{{\textbf {Andrei Arusoaie}} and Daniel Ionu{\c t} Vicol}
\date{Alexandru Ioan Cuza, University of Ia{\c s}i}

\begin{document}

\frame{\titlepage}

\section[Outline]{}
\frame{\tableofcontents}

\section{Introduction}
\subsection{The \K Framework}
\frame{
	\frametitle{The \K Framework}
	\begin{itemize}
	\item \K - framework for defining operational semantics of programming languages
	\end{itemize}
	\begin{itemize}
	\item<1> Imperative: IMP, SIMPLE (untyped, typed), {\textbf{C}}
	\item<1> Object Oriented: KOOL (untyped, typed), {\textbf{Java}}
	\item<1> Assembly: SSRISC, Verilog
	\item<1> Functional: Scheme, Haskell
	\end{itemize}
}

\frame{
	\frametitle{The \K Framework}
	\begin{enumerate}
	\item<1-> Semantics
	\begin{enumerate}
	\item configuration - nested structure of cells
	\item {\it k} - computations cell
	\item \K rules - rewriting rules
	\end{enumerate}
	\item<2-> Syntax
	\begin{enumerate}
	\item internal - using Backus-Naur Form (BNF)
	\item {\it external}
	\end{enumerate}
	\end{enumerate}
}


\subsection{Motivation}
\frame{
	\frametitle{Example: IMP}
	\begin{figure}
	\fontsize{9}{10}
	\selectfont
\begin{center}
\begin{tabular}{|l l l|}
	\hline
	Int & $::=$ & the domain of (unbounded)\\
	&& integer numbers \\
	Bool & $::=$ & the domain of Booleans\\
	Id & $::=$ & standard identifiers \\
	$AExp$ & $::=$ & Int \\
	 & \hspace{7pt}$|$ & Id \\
	 & \hspace{7pt}$|$ & $AExp$ + $AExp$\\
	 & \hspace{7pt}$|$ & $AExp$ / $AExp$\\
	$BExp$ & $::=$ & Bool \\
	 & \hspace{7pt}$|$ & not $BExp$ \\
	 & \hspace{7pt}$|$ & $AExp$ <= $AExp$\\
	 & \hspace{7pt}$|$ & $BExp$ and $BExp$\\
	 $Stmt$ & $::=$ & skip\\
	 & \hspace{7pt}$|$ & $Id$ $:=$ $AExp$\\
	 & \hspace{7pt}$|$ & $Stmt$ ; $Stmt$\\
	 & \hspace{7pt}$|$ & $if$ $BExp$ then $Stmt$ else $Stmt$\\
	 & \hspace{7pt}$|$ & while $BExp$ $do$ $Stmt$\\
	 $Ids$ & $::=$ & List\{Id\}\\
	$Pgm$ & $::=$ & var $Ids$ ; $Stmt$ \\
 	\hline
\end{tabular}
\end{center}
\end{figure}
}

\frame{
	\frametitle{\K AST}
	\begin{itemize}
	\item<1-> {\tt var a,b;\\
	 a := a + 45}
	\item<2-> {\tt 'var\_;\_('\_.\_(id(a),id(b)), '\_;\_('\_:=\_(id(a),'\_+\_(id(a),int(45)))))}
	\end{itemize}
}

\frame{
	\frametitle{\K AST}
	\begin{itemize}
	\item<1-> {\tt var a,b;\\
	 a := {\color{blue}a + 45}}
	\item<1-> {\tt 'var\_;\_('\_.\_(id(a),id(b)), '\_;\_('\_:=\_(id(a),{\color{blue}'\_+\_(id(a),int(45))})))}
	\end{itemize}
}

\frame{
	\frametitle{Motivation}
	\begin{itemize}
	\item<1-> \K's parser works for simple languages
	\item<1-> ... but, it doesn't scale for real-life languages: C, Python, Java
	\item<1-> Solution: use an external parser
	\item<1-> Hard to use an existing parser
	\item<2-> {\color{red}Make it easy to adapt existing parsers for use with \K}
	\end{itemize}
}

\section{Automatize AST construction}
\frame{
	\frametitle{Problem}
	\begin{itemize}
	\item<1-> Let $L$ be a programming language
	\item<1-> Let $G$ be a grammar for $L$
	\item<1-> Let $P_G$ be the parser generated from $G$
	\item<2-> Solution: annotate $G$'s production rules = $G'$
	\item<2-> $P_{G'}$ should output an AST (Abstract Syntax Tree)
	\end{itemize}
}

\subsection{Problem}
\frame{
	\frametitle{Problem}
	Input:
	\begin{itemize}
	\item Grammar $G$
	\item Training set:\\ \{$(p,p_{ast})$ : $p$ - program, $p_{ast}$ - $p$'s corresponding AST\}
	\end{itemize}
	Output:
	\begin{itemize}
	\item Annotated $G$
	\end{itemize}
}

\frame{
	\frametitle{Algorithm}
	\begin{itemize}
	\item For each pair $(p$,$p_{ast})$:\\
	\hspace{1cm}process the parse tree of $p$\\
	\hspace{1cm}until it has the same structure as $p_{ast}$.
	\item Synchronize the trees
	\end{itemize}
}

\frame{
	\frametitle{Algorithm}
	\begin{enumerate}
	\item Annotate production rules
	\item Eliminate ``non-productive'' rules
	\item Eliminate terminal nodes
	\item Adjust the parse tree using the edit distance between two trees
	\item Collect mappings
	\end{enumerate}
}

\subsection{Example}
\frame{
	\frametitle{Annotate production rules}
	\begin{center}
\small{
{\tt
\begin{tabular}{l l l l}
	$AExp$ & $::=$ & Int & {\color{white} [AExp\_0]}\\
	 & \hspace{7pt}$|$ & Id & {\color{white} [AExp\_1]}\\
	 & \hspace{7pt}$|$ & $AExp$ + $AExp$ & {\color{white} [AExp\_2]}\\
	 & \hspace{7pt}$|$ & $AExp$ / $AExp$ & {\color{white} [AExp\_3]}\\
\end{tabular}
}}
\end{center}
}

\frame{
	\frametitle{Annotate production rules}
	\begin{center}
\small{
{\tt
\begin{tabular}{l l l l}
	$AExp$ & $::=$ & Int & {\color{blue} [AExp\_0]}\\
	 & \hspace{7pt}$|$ & Id & {\color{blue} [AExp\_1]}\\
	 & \hspace{7pt}$|$ & $AExp$ + $AExp$ & {\color{blue} [AExp\_2]}\\
	 & \hspace{7pt}$|$ & $AExp$ / $AExp$ & {\color{blue} [AExp\_3]}\\
\end{tabular}
}}
\end{center}
}


\frame{
	\frametitle{Parse tree}

\begin{tabular}{l c r}
& &
\vspace{1.5cm}
\begin{minipage}{.45\linewidth}
	\begin{center}
\fontsize{6}{4}
\selectfont
{\tt
\begin{tabular}{l l l l}
	$AExp$ & $::=$ & Int & {\color{blue} [AExp\_0]}\\
	 & \hspace{7pt}$|$ & Id & {\color{blue} [AExp\_1]}\\
	 & \hspace{7pt}$|$ & $AExp$ + $AExp$ & {\color{blue} [AExp\_2]}\\
	 & \hspace{7pt}$|$ & $AExp$ / $AExp$ & {\color{blue} [AExp\_3]}\\
\end{tabular}
}
\end{center}
\end{minipage}
\\

\begin{minipage}{.45\linewidth}
\begin{center}
{\tt a + 45} 
\end{center}
\end{minipage}
& $\to$ &
\begin{minipage}{.45\linewidth}
\begin{center}
\small{
{\tt
\begin{tabular}{l l l}
AExp\_2&\\
&\hspace{-1cm}AExp\_1&\\
&&\hspace{-1cm}Id\_0(a)\\
&\hspace{-1cm}AExp\_0&\\
&&\hspace{-1cm}Int\_0(45)\\
\end{tabular}}}
\end{center}
\end{minipage}
\end{tabular}
}

\frame{
	\frametitle{Eliminate ``non-productive'' grammar rules}

\begin{tabular}{l c r}
& &
\vspace{1.5cm}
\begin{minipage}{.45\linewidth}
	\begin{center}
\fontsize{6}{4}
\selectfont
{\tt
\begin{tabular}{l l l l}
	$AExp$ & $::=$ & Int & {\color{blue} [AExp\_0]}\\
	 & \hspace{7pt}$|$ & Id & {\color{blue} [AExp\_1]}\\
	 & \hspace{7pt}$|$ & $AExp$ + $AExp$ & {\color{blue} [AExp\_2]}\\
	 & \hspace{7pt}$|$ & $AExp$ / $AExp$ & {\color{blue} [AExp\_3]}\\
\end{tabular}
}
\end{center}
\end{minipage}
\\

\begin{minipage}{.45\linewidth}
\begin{center}
\small{
{\tt
\begin{tabular}{l l l}
AExp\_2&\\
&\hspace{-1cm}{\color{red}AExp\_1}&\\
&&\hspace{-1cm}Id\_0(a)\\
&\hspace{-1cm}{\color{red}AExp\_0}&\\
&&\hspace{-1cm}Int\_0(45)\\
\end{tabular}}}
\end{center}
\end{minipage}
& $\to$ &
\begin{minipage}{.45\linewidth}
\begin{center}
\small{
{\tt
\begin{tabular}{l l}
AExp\_2&\\
&\hspace{-1cm}Id\_0(a)\\
&\hspace{-1cm}Int\_0(45)\\
\end{tabular}}}
\end{center}
\end{minipage}
\end{tabular}
}


\frame{
	\frametitle{Eliminate terminal nodes from the AST, parse tree}

\begin{tabular}{l c r}

\begin{minipage}{.45\linewidth}
\begin{center}
\small{
{\tt
\begin{tabular}{l l}
AExp\_2&\\
&\hspace{-1cm}Id\_0{\color{red}(a)}\\
&\hspace{-1cm}Int\_0{\color{red}(45)}\\
\end{tabular}}}
\end{center}
\end{minipage}
& $\to$ &
\begin{minipage}{.45\linewidth}
\begin{center}
\small{
{\tt
\begin{tabular}{l l}
AExp\_2&\\
&\hspace{-1cm}Id\_0\\
&\hspace{-1cm}Int\_0\\
\end{tabular}}}
\end{center}
\end{minipage}\\\\


\begin{minipage}{.45\linewidth}
\begin{center}
{\tt '\_+\_(id{\color{red}(a)},int{\color{red}(45)})}
\end{center}
\end{minipage}
& $\to$ &
\begin{minipage}{.45\linewidth}
\begin{center}
{\tt '\_+\_(id,int)}
\end{center}
\end{minipage}
\end{tabular}
}



\frame{
	\frametitle{Parse tree vs. AST}
\begin{itemize}
\item Compare parse tree and AST
\item Compute the edit distance between parse tree and AST
\item Total cost of: $insert$, $delete$, $modify$ (0)\\
\end{itemize}

\begin{tabular}{l c r}
\begin{minipage}{.45\linewidth}
\begin{center}
\small{
{\tt
\begin{tabular}{l l}
AExp\_2&\\
&\hspace{-1cm}Id\_0\\
&\hspace{-1cm}Int\_0\\
\end{tabular}}}
\end{center}
\end{minipage}
& $vs.$ &
\begin{minipage}{.45\linewidth}
\begin{center}
{\tt '\_+\_(id,int)}
\end{center}
\end{minipage}
\end{tabular}
}

\frame{
	\frametitle{Assign label to production}

\begin{tabular}{l c r}
\begin{minipage}{.45\linewidth}
\begin{center}
\small{
{\tt
\begin{tabular}{l l}
AExp\_2&\\
&\hspace{-1cm}Id\_0\\
&\hspace{-1cm}Int\_0\\
\end{tabular}}}
\end{center}
\end{minipage}
& $vs.$ &
\begin{minipage}{.45\linewidth}
\begin{center}
{\tt '\_+\_(id,int)}
\end{center}
\end{minipage}
\end{tabular}
\begin{itemize}
\item edit distance = 0
\end{itemize}

\begin{center}
\small{
{\tt
\begin{tabular}{l l l l}
	$AExp$ & $::=$ & Int & \\
	 & \hspace{7pt}$|$ & Id & \\
	 & \hspace{7pt}$|$ & $AExp$ + $AExp$ & {\color{blue} [AExp\_2]}\\
	 & \hspace{7pt}$|$ & $AExp$ / $AExp$ & \\
\end{tabular}
}}
\end{center}
}

\frame{
	\frametitle{Assign label to production}

\begin{tabular}{l c r}
\begin{minipage}{.45\linewidth}
\begin{center}
\small{
{\tt
\begin{tabular}{l l}
{\color{blue} AExp\_2}&\\
&\hspace{-1cm}Id\_0\\
&\hspace{-1cm}Int\_0\\
\end{tabular}}}
\end{center}
\end{minipage}
& $vs.$ &
\begin{minipage}{.45\linewidth}
\begin{center}
{\tt {\color{blue}'\_+\_}(id,int)}
\end{center}
\end{minipage}
\end{tabular}
\begin{itemize}
\item edit distance = 0
\end{itemize}

\begin{center}
\small{
{\tt
\begin{tabular}{l l l l}
	$AExp$ & $::=$ & Int & \\
	 & \hspace{7pt}$|$ & Id & \\
	 & \hspace{7pt}$|$ & $AExp$ + $AExp$ & {\color{red} [AExp\_2]}\\
	 & \hspace{7pt}$|$ & $AExp$ / $AExp$ & \\
\end{tabular}
}}
\end{center}
}


\frame{
	\frametitle{Assign label to production}

\begin{tabular}{l c r}
\begin{minipage}{.45\linewidth}
\begin{center}
\small{
{\tt
\begin{tabular}{l l}
{\color{blue} AExp\_2}&\\
&\hspace{-1cm}Id\_0\\
&\hspace{-1cm}Int\_0\\
\end{tabular}}}
\end{center}
\end{minipage}
& $vs.$ &
\begin{minipage}{.45\linewidth}
\begin{center}
{\tt {\color{blue}'\_+\_}(id,int)}
\end{center}
\end{minipage}
\end{tabular}
\begin{itemize}
\item edit distance = 0
\end{itemize}

\begin{center}
\small{
{\tt
\begin{tabular}{l l l l}
	$AExp$ & $::=$ & Int & \\
	 & \hspace{7pt}$|$ & Id & \\
	 & \hspace{7pt}$|$ & $AExp$ + $AExp$ & {\tt {\color{red} ['\_+\_]}}\\
	 & \hspace{7pt}$|$ & $AExp$ / $AExp$ & \\
\end{tabular}
}}
\end{center}
}



\section{Results}
\frame{
	\frametitle{Results}
	\begin{itemize}
	\item Implementation: ANTLR + Java
	\end{itemize}
	
	\begin{table}[!Htp]
%\caption{Time to collect and analyze data}
\fontsize{7}{8}
\selectfont
\centering
\begin{tabular} {c c c c c}
\hline
Language&Example&No. of covered& Tree &Annotate\\
&NO.&productions&synchronization&productions\\
&&&(ms)&(ms)\\ [0.5ex]
\hline\hline
IMP & \#1 & 22 & 50 & 1 \\[0.5ex]
\hline
 & \#1 & 18 & 51 & 1 \\
 & \#2 & 20 &  66 & 2 \\
SIMPLE\_UNTYPED & \#3 & 30 & 53 & 4 \\
 & \#4 & 12 & 20 & 0 \\
 & \#5 & 25 & 37 & 1 \\[0.5ex]
\hline
	&\#1 & 40 &  74 & 5\\
	&\#2 & 25 &  60 & 3\\
	&\#3 & 62 &  133 & 7\\
JAVA-CORE&\#4 & 36 &  58 & 5\\
	&\#5 & 23 &  42 & 4\\
	&\#6 & 11 &  25 & 0\\
	&\#7 & 5 & 4 & 0\\[0.5ex]
\hline
\end{tabular}
\label{eval:analyze}
\end{table}
	
}

\section{Conclusions \& Future work}
\frame{
	\frametitle{Conclusions}
	\begin{itemize}
	\item<1-> Given $G$, set of pairs $(p$,$p_{ast})$ $\to$ annotated $G$
	\item<2-> Implementation: ANTLR + Java
	\item<3-> Tests
	\end{itemize}
}
\frame{
	\frametitle{Future work}
	\begin{itemize}
	\item<1-> Treat ambiguities
	\item<2-> Extracting grammar from programs
	\end{itemize}
}

\frame{
	\frametitle{Thank you}
	\begin{center}
	\fontsize{16}{16}
	\selectfont
	Questions?\\
	\end{center}
	Links:
	\begin{itemize}
	\item The tool:\\ {\color{blue}\url{http://code.google.com/p/ast-generator}}
	\item The \K Framework:\\ {\color{blue}\url{http://k-framework.org}}
	\end{itemize}
}

\end{document}
